<head>
    <meta charset="UTF-8">
<title>算法提高 打水问题</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p><span style="font-family: 宋体; color: black; font-size: 12pt; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt"><strong>问题描述<span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US">N</span><span>个人要打水，有<span lang="EN-US">M</span>个水龙头，第<span lang="EN-US">i</span>个人打水所需时间为<span lang="EN-US">Ti</span>，请安排一个合理的方案使得所有人的等待时间之和尽量小。<o:p></o:p></span></p>
<p style="text-align: left; text-indent: 17.25pt; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US">&nbsp;</span><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US"><o:p></o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; font-size: 12pt; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt"><strong>输入<span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt">第一行两个正整数<span lang="EN-US">N M </span>接下来一行<span lang="EN-US">N</span>个正整数<span lang="EN-US">Ti</span>。<span lang="EN-US"><o:p></o:p></span></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US">N,M&lt;=1000</span><span>，<span lang="EN-US">Ti&lt;=1000</span><o:p></o:p></span></p>
<p style="text-align: left; text-indent: 17.25pt; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US">&nbsp;</span><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US"><o:p></o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; font-size: 12pt; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt"><strong>输出<span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span>最小的等待时间之和。（不需要输出具体的安排方案）<o:p></o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US"><o:p>&nbsp;</o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; font-size: 12pt; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt"><strong>样例输入<span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US">7 3<o:p></o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span>3 6 1 4 2 5 7<o:p></o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US"><o:p>&nbsp;</o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; font-size: 12pt; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt"><strong>样例输出<span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US">11<o:p></o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="font-family: 宋体; color: black; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-size: 10.5pt" lang="EN-US"><o:p>&nbsp;</o:p></span></p>
<p style="text-align: left; margin: 0cm 0cm 0pt; background: white; mso-margin-top-alt: auto; mso-margin-bottom-alt: auto; mso-pagination: widow-orphan" class="MsoNormal" align="left"><span style="color: #ff0000"><span style="font-family: 宋体; font-size: 12pt; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt"><strong>提示</strong></span></span><span style="font-family: 宋体; color: black; font-size: 12pt; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-family: 宋体; mso-font-kerning: 0pt"><strong><span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="color: #000000"><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt">一种最佳打水方案是，将<span lang="EN-US">N</span>个人按照<span lang="EN-US">Ti</span>从小到大的顺序依次分配到<span lang="EN-US">M</span>个龙头打水。</span></span><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="color: #000000"><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt">例如样例中，<span lang="EN-US">Ti</span>从小到大排序为<span lang="EN-US">1</span>，<span lang="EN-US">2</span>，<span lang="EN-US">3</span>，<span lang="EN-US">4</span>，<span lang="EN-US">5</span>，<span lang="EN-US">6</span>，<span lang="EN-US">7</span>，将他们依次分配到<span lang="EN-US">3</span>个龙头，则去龙头一打水的为<span lang="EN-US">1</span>，<span lang="EN-US">4</span>，<span lang="EN-US">7</span>；去龙头二打水的为<span lang="EN-US">2,5</span>；去第三个龙头打水的为<span lang="EN-US">3,6</span>。</span></span><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="color: #000000"><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt">第一个龙头打水的人总等待时间<span lang="EN-US"> = 0 + 1 + (1 + 4) = 6</span></span></span><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="color: #000000"><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt">第二个龙头打水的人总等待时间<span lang="EN-US"> = 0 + 2 = 2</span></span></span><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="color: #000000"><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt">第三个龙头打水的人总等待时间<span lang="EN-US"> = 0 + 3 = 3</span></span></span><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="color: #000000"><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt">所以总的等待时间<span lang="EN-US"> = 6 + 2 + 3 = 11</span></span></span><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="color: #ff0000"><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt" lang="EN-US"><o:p><span style="color: #000000">&nbsp;</span></o:p></span></span><span style="font-family: 宋体; mso-ascii-theme-font: minor-fareast; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-fareast; mso-bidi-font-size: 10.5pt" lang="EN-US"><o:p></o:p></span></p>
<p><span style="display: none" id="1288812791115E">&nbsp;</span></p>